package Solution.problem056;

import java.util.*;

/**
 * @program Leetcode
 * @description:
 * 给出很多个区间，合并有重叠的区间，输出最后的结果。我们分析可以得知对于两个区间interval1和interval2，如果interval1.start<=interval2.start,有一下几种情况：
 *
 * (1)interval1.end<interval2.start ， 两个区间没有交叠 ， 那么两个区间都加入结果集中   *
 * （2） i n t e rval1.end>=interval2.start，有交叠，如果A、interval1.end>=interval2.end，
 * 那interval2是interval1的子区间，将interval1加入，然后跳过interval2；
 * B、interval1.end<interval2.end，合并两个区间，将新区间加入结果中。
 *
 * 所以我们可以对给出的区间先按照strat升序排列，对于start相同的，按照end升序排序，在按照上面的方法遍历区间集就可以得出最后的结果：
 * @author: lishangsheng
 * @create: 2019/05/30 09:38
 */
public class Solution {
    public static int[][] merge(int[][] intervals) {
        if(intervals.length<=1){
            return intervals;
        }
        int colEnd=intervals[0].length-1;
        Map<Integer,Integer> seMap=new HashMap<Integer, Integer>();
        List<Integer> keys=new ArrayList<Integer>();
        /*第一遍遍历，去掉开头重复的*/
        for(int i=0;i<intervals.length;i++) {
            int startValue = intervals[i][0];
            int endValue = intervals[i][colEnd];

            if (seMap.containsKey(startValue)) {
                int oldValue = seMap.get(startValue);
                if (oldValue < endValue) {
                    seMap.put(startValue, endValue);
                }
            }else{
                keys.add(startValue);
                seMap.put(startValue,endValue);
            }
        }
        Collections.sort(keys);

        int maxValueKey=keys.get(0);
        int maxValue=seMap.get(maxValueKey);
        for(Integer key:keys){
            int endValue=seMap.get(key);
            if(key>maxValueKey&&endValue>=maxValue){

                //1,4;2,5
                if(key<=maxValue){
                    /* 将1的value更新成5*/
                    seMap.put(maxValueKey,endValue);
                    /* 将2，5删掉*/
                    seMap.remove(key);
                    maxValue=endValue;
                }else {
                    maxValue=endValue;
                    maxValueKey=key;
                }
            }else if(key > maxValueKey){
                //1,4;2,3
                seMap.remove(key);
            }

        }

        /*拼装结果*/
        int[][] result=new int[seMap.size()][2];
        Iterator<Map.Entry<Integer, Integer>> iterator =seMap.entrySet().iterator();

        int i=0;
        while (iterator.hasNext()) {
            Map.Entry<Integer,Integer> elem = iterator.next();
            result[i][0]=elem.getKey();
            result[i][1]=elem.getValue();
            i++;
        }
        return result;
    }

    public static void main(String[] args) {
/*       int[][] array = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] result = merge(array);
        System.out.println(JSON.toJSONString(result));

        int[][] array2 = new int[][]{{1, 4}, {4, 5}};
        int[][] result2 = merge(array2);
        System.out.println(JSON.toJSONString(result2));

        int[][] array3 = new int[][]{{1, 4}, {0, 4}};
        int[][] result3 = merge(array3);
        System.out.println(JSON.toJSONString(result3));*/

        //[[2,3],[2,2],[3,3],[1,3],[5,7],[2,2],[4,6]]

        int[][] array4 = new int[][]{{2, 3}, {2, 2},{3,3},{1,3},{5,7},{2,2},{4,6}};
        int[][] result4 = merge(array4);
        System.out.println(result4);


    }
}
